import java.util.ArrayList;

public class RadixSort {
    public static void radixSort(int[] arr) {


        int max = 0;
        for (int n : arr)
            max = Math.max(max, n);

        int maxDigit =String.valueOf(max).length();//获取最大数字的位数

        int mod = 10, div = 1;

        ArrayList<ArrayList<Integer>> list = new ArrayList<>();

        for (int i = 0; i < 10; i++)//分配10个桶，每个桶代表0-9的数
            list.add(new ArrayList<>());

        for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
            for (int j = 0; j < arr.length; j++) {//分配桶
                int index = Math.abs((arr[j] % mod) / div);
                list.get(index).add(arr[j]);
            }

            int index = 0;
            for (int j = 0; j < list.size(); j++){//将桶中数据重新分配
               while (list.get(j).size()>0)
                   arr[index++]=list.get(j).remove(0);
            }
        }
    }
}
